/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/k-closest-points
   @Language: C++
   @Datetime: 19-04-05 09:03
   */


/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */

class Solution {
	typedef pair<Point,long> POINT;
	struct comp{
		bool operator()(const POINT &a, const POINT &b)const{
			if(a.second==b.second)
				if(a.first.x==b.first.x) return a.first.y<b.first.y;
				else return a.first.x<b.first.x;
			return a.second<b.second;
		}
	};
public:
	/**
	 * @param points: a list of points
	 * @param origin: a point
	 * @param k: An integer
	 * @return: the k closest points
	 */
	vector<Point> kClosest(vector<Point> &points, Point &origin, int k) {
		// write your code here
		priority_queue<POINT,vector<POINT>,comp> heap;	// maxheap
		for(const auto &p:points){
			long dist=(long)(p.x-origin.x)*(p.x-origin.x)+(long)(p.y-origin.y)*(p.y-origin.y);
			heap.push(make_pair(p,dist));
			if(heap.size()>k) heap.pop();
		}
		vector<Point> vp(k);
		for(; heap.size(); heap.pop()){
			const auto &p=heap.top();
			vp[heap.size()-1]=p.first;
		}
		return vp;
	}
};
